//希尔排序

#pragma once

//希尔排序
template <typename E>
void ShellSort(E a[],int n)
{
    int dk = n / 2;
    while(dk >= 1){
        //一趟增量 dk 的希尔排序
        for(int i = dk; i<n ; i++){
            E x = a[i];
            int j;
            for(j = i - dk; j >= 0 && x < a[j] ; j -= dk)
                a[j +dk] = a[j];
            a[j + dk] = x;
        }

        //缩小增量
        dk /= 2;
    }
}